# Updated on 2013/09/10 night

from __future__ import division
from operator import itemgetter, attrgetter


import gc
import heapq
import math
import matplotlib
import numpy as np
import os
import pylab
import random
from sets import Set
from scipy import stats
import sys
import time

print "Program Begins..."
# Put the most desired postings into the baby pruned index

########################################################################
# option1:
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX = 6451948010 # 100% of the whole index, including ALL the postings
# option2:
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX = 531285 # for debug of the input file 1
# option3:
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX = 182 # for debug of the input file 1 line1

# index = 0
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_1Percent_kept: 64519480
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_1Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.01 )
# index = 1
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_5Percent_kept: 322597400
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_5Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.05 )
# index = 2
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_10Percent_kept: 645194801
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_10Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.1 )
# index = 3
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_20Percent_kept: 1290389602
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_20Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.2 )
# index = 4
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_30Percent_kept: 1935584403
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_30Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.3 )
# index = 5
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_40Percent_kept: 2580779204
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_40Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.4 )
# index = 6
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_50Percent_kept: 3225974005
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_50Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.5 )
# index = 7
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_60Percent_kept: 3871168806
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_60Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.6 )
# index = 8
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_70Percent_kept 4516363607
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_70Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.7 )
# index = 9
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_80Percent_kept: 5161558408
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_80Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.8 )
# index = 10
# TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_90Percent_kept: 5806753209
TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_90Percent_kept = int( TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX * 0.9 )


print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_1Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_1Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_5Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_5Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_10Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_10Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_20Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_20Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_30Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_30Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_40Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_40Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_50Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_50Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_60Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_60Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_70Percent_kept",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_70Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_80Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_80Percent_kept 
print "TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_90Percent_kept:",TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_90Percent_kept


LIST_FOR_STORING_THRESHOLD_NUMBERS = []
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_1Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_5Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_10Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_20Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_30Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_40Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_50Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_60Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_70Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_80Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX_90Percent_kept)
LIST_FOR_STORING_THRESHOLD_NUMBERS.append(TOTAL_NUM_OF_DESIGNED_POSTINGS_IN_THE_INVERTED_INDEX)

# for debug ONLY
print "len(LIST_FOR_STORING_THRESHOLD_NUMBERS):",len(LIST_FOR_STORING_THRESHOLD_NUMBERS)

# This is ONLY one list, and this list will contain 25M tuples, each tuple will have the following format(the current largest value, docIndex, the actual document posting list). And Of course for each document list, it will contain all the current un_popped postings for that document 
originalMotherListOfAllDocumentPostingList = []

# key: docIndex in int format
# value: list containing all the postings being selected for this document
currentPrunedPostingListWithDocIndexDict = {}

# total # of postings counted and take into consideration
totalNumOfPostingsCounted = 0

inputFileName = "/data3/obukai/workspace/web-search-engine-wei/polyIRIndexer/forwardIndexExperimentalRepresentation20130909_NEW"
inputFileHandler = open(inputFileName,"r")



# init
docIndex = 0
currentLine = inputFileHandler.readline()
while currentLine:
    currentLineElements = currentLine.strip().split(" ")
    print "docIndex:",docIndex
    print "# of postings:",int( len(currentLineElements[2:])/3 )
    print
    currentDocTrecID = currentLineElements[0]
    currentDocDocID = currentLineElements[1]
    # Updated by Wei 2013/09/09 night
    # This document identifier can be as the trecID external, or the docID internal, OR simply just the docIndex
    currentDocIdentifier = currentDocTrecID
    numOfPostingsRecordedForCurrentDocument = int(currentLineElements[2])
    ##############################################
    currentDocumentPostingList = []
    
    if numOfPostingsRecordedForCurrentDocument != len(currentLineElements[3:])/3:
        print "critical format problem in the input file"
        exit(1)
    else:
        # OK for passing
        pass
    
    baseIndex = 3
    step = 3
    for i in range(0,numOfPostingsRecordedForCurrentDocument):
        currentTerm = currentLineElements[baseIndex + step * i]
        currentTermScore = float( currentLineElements[baseIndex + step * i + 1] )
        currentTermFakePart1Probability = -float( currentLineElements[baseIndex + step * i + 2] )
        currentDocumentPostingList.append( (currentTerm,currentTermScore,currentTermFakePart1Probability) )
    totalNumOfPostingsCounted += len(currentDocumentPostingList)
    # sorted by the actual probability we give
    currentDocumentPostingList.sort(cmp=None, key=itemgetter(2), reverse=False)
    (_,_,currentMostPromisingPostingProbabilityForThisDocument) = currentDocumentPostingList[0]
    currentHeapTuple = (currentMostPromisingPostingProbabilityForThisDocument,currentDocIdentifier,currentDocumentPostingList)
    originalMotherListOfAllDocumentPostingList.append(currentHeapTuple)  
    
    
    
    docIndex += 1
    # for debug
    if docIndex == 2:
        break
    
    currentLine = inputFileHandler.readline()
    
inputFileHandler.close()



print "totalNumOfPostingsCounted:",totalNumOfPostingsCounted
print "len(originalMotherListOfAllDocumentPostingList):",len(originalMotherListOfAllDocumentPostingList)
print "# of document posting LOAD:",docIndex

# The 1st time heap init
# Is it really take just take a few MS
heapq.heapify(originalMotherListOfAllDocumentPostingList)

# correctness check
totalNumOfPostings = 0
tempList = []
for currentTuple in originalMotherListOfAllDocumentPostingList:
    (_,_,tempList) = currentTuple
    totalNumOfPostings += len(tempList)
print "--->(before)total # Of Postings in BIG heap:",totalNumOfPostings
print "--->(before)originalMotherListOfAllDocumentPostingList check:"
for currentHeapTuple in originalMotherListOfAllDocumentPostingList:
    (currentMostPromisingPostingProbabilityForThisDocument,currentDocIdentifier,currentDocumentPostingList) = currentHeapTuple
    print "currentDocIdentifier:",currentDocIdentifier
    print "currentMostPromisingPostingProbabilityForThisDocument:",currentMostPromisingPostingProbabilityForThisDocument
    print "len(currentDocumentPostingList):",len(currentDocumentPostingList)
    # print "currentDocumentPostingList:",currentDocumentPostingList
    print

# the variables I used through the WHOLE construction process
# The OLD ones
# currentOLDMostPromisingPostingValueInDoc in float format
# currentOLDDocTrecID in int format
# currentOLDDocPostingList in list format

# The relative NEW ones
# currentNEWMostPromisingPostingValueInDoc in float format
# currentNEWDocIndex in int format
# currentNEWDocPostingList in list format(ignore this cause I do NOT want to do the whole data COPY of this) 

currentOLDMostPromisingPostingValueInDoc = 1.0
currentOLDDocTrecID = ""
currentOLDDocPostingList = []

currentNEWMostPromisingPostingValueInDoc = 1.0
currentNEWDocIndex = ""
# currentNEWDocPostingList = []

# Just 1 turn for the correctness check
currentTotalNumOfPostingsGathered = 0
currentTotalNumOfPostingsPopFromOriginalBigHeap = 0
for j in range(1,2):
    print "j:",j
    print "# of postings needed to pick:",LIST_FOR_STORING_THRESHOLD_NUMBERS[j]
    # print "--->len(originalMotherListOfAllDocumentPostingList):",len(originalMotherListOfAllDocumentPostingList)
    currentHeapMinTuple = heapq.heappop(originalMotherListOfAllDocumentPostingList)
    # print "--->len(originalMotherListOfAllDocumentPostingList):",len(originalMotherListOfAllDocumentPostingList)
    (currentOLDMostPromisingPostingValueInDoc,currentOLDDocTrecID,currentOLDDocPostingList) = currentHeapMinTuple
    
    # condition check
    (_,_,currentOLDValueInDocAtTheBeginningOfList) = currentOLDDocPostingList[0]
    if currentOLDMostPromisingPostingValueInDoc != currentOLDValueInDocAtTheBeginningOfList:
        print "basic critical ERROR, mark1"
        exit(1)
    else:
        pass
    
    currentTotalNumOfPostingsGathered = 0
    while currentTotalNumOfPostingsGathered <= LIST_FOR_STORING_THRESHOLD_NUMBERS[j]:
        print "currentOLDMostPromisingPostingValueInDoc:",currentOLDMostPromisingPostingValueInDoc
        # for debug
        # print "currentTotalNumOfPostingsGathered:",currentTotalNumOfPostingsGathered
        # the construction process of the currentPrunedIndex
        # if there are any postings have the same score in the current document
        numOfSameScorePostingsInCurrentDoc = 1
        (currentTerm,_,_) = currentOLDDocPostingList[numOfSameScorePostingsInCurrentDoc-1]
        (_,_,currentOLDValueInDocAtList) = currentOLDDocPostingList[numOfSameScorePostingsInCurrentDoc]
        while currentOLDMostPromisingPostingValueInDoc == currentOLDValueInDocAtList:
            numOfSameScorePostingsInCurrentDoc += 1
            (currentTerm,_,_) = currentOLDDocPostingList[numOfSameScorePostingsInCurrentDoc-1]
            (_,_,currentOLDValueInDocAtList) = currentOLDDocPostingList[numOfSameScorePostingsInCurrentDoc]
        print "--->numOfSameScorePostingsInCurrentDoc:",numOfSameScorePostingsInCurrentDoc
        # step1: put the current being picked posting into the currentPrunedMotherListOfAllDocumentPostingList
        # init the new doc posting list if necessary
        if currentOLDDocTrecID not in currentPrunedPostingListWithDocIndexDict:
            currentPrunedPostingListWithDocIndexDict[currentOLDDocTrecID] = {} 
        else:
            pass
        
        # All I need the info about the posting is just the (trecID,term) pair or (docID,term) pair
        for i in range(0,numOfSameScorePostingsInCurrentDoc):
            currentTotalNumOfPostingsPopFromOriginalBigHeap += 1
            if currentTerm not in currentPrunedPostingListWithDocIndexDict[currentOLDDocTrecID]:
                currentPrunedPostingListWithDocIndexDict[currentOLDDocTrecID][currentTerm] = 1
                currentTotalNumOfPostingsGathered += 1
                print "currentOLDDocTrecID:",currentOLDDocTrecID
                print "currentTerm:",currentTerm
                # print "currentOLDMostPromisingPostingValueInDoc:",currentOLDMostPromisingPostingValueInDoc
                print "currentTotalNumOfPostingsGathered:",currentTotalNumOfPostingsGathered
            else:
                print "the posting for the term'",currentTerm,"'has been selected before."

        print 
        
        # step2:
        # construction of the newTestTuple and push it back to the originalMotherListOfAllDocumentPostingList
        (_,_,currentOLDValueInDocAtList) = currentOLDDocPostingList[numOfSameScorePostingsInCurrentDoc]
        currentNEWMostPromisingPostingValueInDoc = currentOLDValueInDocAtList
        currentNEWDocIndex = currentOLDDocTrecID
        currentHeapMinTuple = heapq.heappushpop(originalMotherListOfAllDocumentPostingList, (currentNEWMostPromisingPostingValueInDoc,currentNEWDocIndex,currentOLDDocPostingList[numOfSameScorePostingsInCurrentDoc:]) )
        # for debug
        # print "currentHeapMinTuple:",currentHeapMinTuple
        (currentOLDMostPromisingPostingValueInDoc,currentOLDDocTrecID,currentOLDDocPostingList) = currentHeapMinTuple
    
    heapq.heappush(originalMotherListOfAllDocumentPostingList, currentHeapMinTuple)

print "overall pruned index statistics:"
print "currentTotalNumOfPostingsGathered:",currentTotalNumOfPostingsGathered
print "currentTotalNumOfPostingsPopFromOriginalBigHeap:",currentTotalNumOfPostingsPopFromOriginalBigHeap
print "currentPrunedPostingListWithDocIndexDict:",currentPrunedPostingListWithDocIndexDict

# correctness check
totalNumOfPostings = 0
tempList = []
for currentTuple in originalMotherListOfAllDocumentPostingList:
    (_,_,tempList) = currentTuple
    totalNumOfPostings += len(tempList)

print "--->(after)total # Of Postings in BIG heap:",totalNumOfPostings
print "--->(after)originalMotherListOfAllDocumentPostingList check:"
for currentHeapTuple in originalMotherListOfAllDocumentPostingList:
    (currentMostPromisingPostingProbabilityForThisDocument,currentDocIdentifier,currentDocumentPostingList) = currentHeapTuple
    print "currentDocIdentifier:",currentDocIdentifier
    print "currentMostPromisingPostingProbabilityForThisDocument:",currentMostPromisingPostingProbabilityForThisDocument
    print "len(currentDocumentPostingList):",len(currentDocumentPostingList)
    # print "currentDocumentPostingList:",currentDocumentPostingList
    print
print "Program Ends."


